Product of Array Except Self || Trapping Rain Water

发表于

Product of Array Except Self

Question

Given an array of n integers where n > 1, nums, return an array outputsuch that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Analysis

LeetCode Discuss Two Pointers

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] product=new int[nums.length];
        int right=1;
        product[0]=1;
        for(int i=1;i<nums.length;i++){
            product[i]=product[i-1]*nums[i-1];
        }
        for(int j=nums.length-1;j>=0;j--){
            product[j]*=right;
            right*=nums[j];
        }
        return product;
    }
}

Trapping Rain Water

Question

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

Analysis

LeetCode Discuss

中文解析

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    public int trap(int[] height) {
        int len=height.length;
        if(len<2)   return 0;
        int[] maxl=new int[len];
        int[] maxr=new int[len];
        int water=0;
        int min=Integer.MAX_VALUE;
        for(int i=1;i<len;i++)
        {
            maxl[i]=Math.max(maxl[i-1],height[i-1]);
        }
        for(int j=len-2;j>=0;j--){
            maxr[j]=Math.max(maxr[j+1],height[j+1]);
            min=Math.min(maxl[j],maxr[j]);
            if(min>height[j])
                water+=min-height[j];
        }
        return water;
    }
}